package com.lwx.chapter4;


public class MaxHeap {
    Integer[] data;
    int capacity;
    //数组中数据的数量
    int count;

    public MaxHeap(int capacity) {
        //从1...capacity的位置存储元素
//        data = (Integer[])new Object[capacity+1];
        data = (Integer[]) new Integer[capacity+1];
        count = 0;
        this.capacity = capacity;
    }

    public MaxHeap(Integer[] arr,int n) {
        //从1...capacity的位置存储元素
//        data = (Integer[])new Object[capacity+1];
        data = (Integer[]) new Integer[n+1];
        this.capacity = n;
        count = 0;
        for (int i = 0; i < arr.length && i<n; i++) {
            count ++;
            data[i+1] = arr[i];
        }
        for (int i = arr.length/2; i>=1 ; i = i--) {
            shiftDown(i);
        }
        for (int i = 0; i < arr.length && i<this.count; i++) {
            arr[i] = data[i+1];
        }
    }

    int size(){
        return count;
    }

    boolean isEmpty(){
        return count==0;
    }

    void insert(Integer t){
        //数组已满
        if(count+1 > capacity){
            return;
        }
        data[count +1] = t;
        count ++;
        shiftUp(count);
    }

    Integer extractMax(){
        if(count > 0){
            Integer ret = data[1];
            Integer temp = data[1];
            data[1] = data[count];
            data[count] = temp;
            count --;
            shiftDown(1);
            return ret;
        }
        return null;
    }

    /**
     * 将k索引位置的元素向上移动，维持最大堆的定义
     * @param k
     */
    public void shiftUp(int k){
        while ( k >1 && data[k/2].compareTo(data[k]) < 0){
            Integer temp = data[k/2];
            data[k/2] = data[k];
            data[k] = temp;
            k /= 2;
        }
    }

    public void shiftDown(int k){
        /**
         * 有左孩子
         */
        while (2*k <= count){
            //代表左右孩子中较大的那一个的下标
            int j = 2*k;
            //有右孩子，且右孩子比左孩子大
            if (j+1 <= count && data[j+1].compareTo(data[j]) >0){
                j = j+1;
            }
            if(data[k].compareTo(data[j]) >= 0){
                break;
            }else {
                Integer temp = data[k];
                data[k] = data[j];
                data[j] = temp;
                k = j;
            }
        }
    }




}
